import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val=x;
        next=null;
    }
}

public class MergeKSortedLists {
    public static ListNode mergeKLists(List<ListNode> lists) {
        if(lists == null || lists.size() == 0) return null;

        return Helper(lists,0,lists.size()-1);
    }
    
    public static ListNode Helper(List<ListNode> lists,int l,int r){
        //System.out.println(l+ " " + r);
        if(l<r){
            int m = (l+r)/2;
            return mergeTwoLists(Helper(lists,l,m),Helper(lists,m+1,r));
        }

        return lists.get(l);
    }
    
    public static ListNode mergeTwoLists(ListNode l1,ListNode l2) {
        //System.out.println("mergeTwoLists");
                       if(l1==null) return l2;
        if(l2==null) return l1;

        ListNode p1 = l1;
        ListNode p2 = l2;

        ListNode p3 = null;

        if(p1.val < p2.val){
            p3 = p1;
            p1 = p1.next;
        }
        else{
            p3 = p2;
            p2 = p2.next;
        }

        ListNode pHead = p3;
        
        while(p1!=null && p2!=null){
            if(p1.val < p2.val) {
                p3.next = p1;
                p1 = p1.next;
                p3 = p3.next;
            }
            else {
                p3.next = p2;
                p2 = p2.next;
                p3 = p3.next;
            }
        }

        if(p1 != null) {
            p3.next = p1;
        }

        if(p2 != null) {
            p3.next = p2;
        }

        return pHead;
    }
    
    public static void main(String[] args) {
ListNode list = new ListNode(0);
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);

        list.next = n1;
        n1.next = n2;
        n2.next = n3;
        
        ListNode list1 = new ListNode(0);
        ListNode n11 = new ListNode(1);
        ListNode n21 = new ListNode(2);
        ListNode n31 = new ListNode(3);

        list1.next = n11;
        n11.next = n21;
        n21.next = n31;
        
        ListNode list2 = new ListNode(0);
        ListNode n12 = new ListNode(1);
        ListNode n22 = new ListNode(2);
        ListNode n32= new ListNode(3);

        list2.next = n12;
        n12.next = n22;
        n22.next = n32;

        ArrayList<ListNode> lists = new ArrayList<ListNode>();
        
        lists.add(list);
        lists.add(list1);
        lists.add(list2);
        
        ListNode result = mergeKLists(lists);

        while(result != null){
            System.out.print(result.val + "\t");
            result = result.next;
        }
        System.out.println();        
    }
}